package a_unionSet;

public class UnionSet {
	private int[] unset;
	private int[] rank;	//记录高度
	
	public UnionSet(){
	}
	
	public void makeSet(int size){
		unset=new int[size];
		rank=new int[size];
		for(int i=0;i<size;i++)
			unset[i]=i;
	}
	
	/**
	 * 找到x所在集合的代表，即树的根节点。可以用来比较两个元素是否在同一个集合中。
	 * 路径压缩:每次查找时，另路径上的每个节点都指向根节点。
	 * @param x
	 * @return
	 */
	public int find(int x){
		if(x!=unset[x])
			unset[x]=find(unset[x]);
		return unset[x]; 
	}
	
	/**
	 * union 有两种策略，一种是将高度较小的树合并到高度较大的树下，另一种是将节点数目较少的树合并到节点多的树下。
	 * @param x
	 * @param y
	 */
	public void union(int x,int y){
		if((x=find(x))==(y=find(y)))return;
		if(rank[x]>rank[y]){
			unset[y]=x;
		}else{
			unset[x]=y;
			if(rank[x]==rank[y])rank[y]++;
		}
	}
	

	/**
	 * 使用第二种策略，只需要维护一个unset数组，
	 * 如果unset的值为正数，则表示父节点的索引；如果unset的值为负数，则表示该元素是
	 * 所在集合的代表，即树根，绝对值为该棵树的元素个数。
	 * 
	 */
	public int find2(int x){
		if(unset[x]<0)return x;
		unset[x]=find2(unset[x]);
		return unset[x];
	}
	
	/**
	 * 如果要获得某个元素所在集合的元素个数，0-unset[find2(x)]
	 * @param x
	 * @param y
	 */
	public void union2(int x,int y){
		if((x=find2(x))==(y=find2(y)))
			return;
		if(unset[x]<unset[y]){
			unset[x]+=unset[y];
			unset[y]=x;
		}else{
			unset[y]+=unset[x];
			unset[x]=y;
		}
	}
}
